package ru.startandroid.firstproj;

public class list <T, Lt> {

	public class node <nT, nLt>
	{
		T data1;
		Lt data2;
		node <nT, nLt> next, prev;
		node (T d1, Lt d2, node <nT, nLt> n, node <nT, nLt> p)
		{
			data1 = d1; data2 = d2; next = n; prev = p; 
		}
	};
	
	private node <T, Lt> head, tail;
	public node <T, Lt> first() 
	{
		if ( head != null ) 
			return head;
		else 
			return null;
	}
	public node <T, Lt> end() 
	{
		if ( tail != null ) 
			return tail;
		else 
			return null;
	}
	list()
	{
		head = null; tail = null;
	}
	list (list <T, Lt> a)
	{
		head = null;
		tail = null;
		if ( a.first() != null ) 
		{
			node <T, Lt> q = a.first();
			do 
			{				
				this.push_back(q.data1, q.data2);
				q = q.next;
			} while( q != null );
		}
	}
	
	public void push_back(T d1, Lt d2)
	{
		if ( head == null ) 
		{
			head = new node <T, Lt> (d1, d2, null, null);
			tail = head;
		}
		else 
		{	
			tail.next = new node <T, Lt> (d1, d2, null, tail);			
			tail = tail.next;
		}
	}
	public void insert_after(T d1, Lt d2, T e)
	{
		node <T, Lt> q = search(e);
		if ( q != null )
			if ( q.next == null )
				this.push_back(d1, d2);
			else
			{
				q.next.prev = new node <T, Lt> (d1, d2, q.next, q);
				q.next = q.next.prev;
			}		
	}
	public void pop(T d1, Lt d2)
	{
		node <T, Lt> q = search(d1, d2);
		if ( q != null )
		{
			if ( q.data1 == head.data1 && q.data2 == head.data2 )
			{
				if ( head.next != null )
				{
					head = head.next;
					head.prev = null;
				}
				else
				{
					head = null;
					tail = null;
				}
			}
			else
				if ( q.data1 == tail.data1 && q.data2 == tail.data2 )
				{
					tail = tail.prev;
					tail.next = null;
				}
				else
				{
					q.prev.next = q.next;
					q.next.prev = q.prev;
				}	
			q = null;
		}
	}
	public void pop(node <T, Lt> q)
	{
		if ( q != null )
		{
			if ( q.data1 == head.data1 && q.data2 == head.data2 )
			{
				if ( head.next != null )
				{
					head = head.next;
					head.prev = null;
				}
				else
				{
					head = null;
					tail = null;
				}
			}
			else
				if ( q.data1 == tail.data1 && q.data2 == tail.data2 )
				{
					tail = tail.prev;
					tail.next = null;
				}
				else
				{
					q.prev.next = q.next;
					q.next.prev = q.prev;
				}
			q = null;
		}
	}
	node <T, Lt> search(T d1) 
	{
		if ( head != null ) 
		{
			node <T, Lt> q = head;
			do 
			{
				if ( q.data1 == d1 ) 
					return q;
				else 
					q = q.next;
			} while ( q != null );
			return null;
		}
		return null;
	}
	node <T, Lt> search(T d1, Lt d2) 
	{
		if ( head != null ) 
		{
			node <T, Lt> q = head;
			do 
			{
				if ( q.data1 == d1 && q.data2 == d2 ) 
					return q;
				else 
					if ( head != tail )
						q = q.next;
					else
						return null;
			} while ( q != null );
			return null;
		}
		return null;
	}
	public void sort()
	{
		node <T, Lt> q = head;		
		do 
		{	
			node <T, Lt> p = q;	
			while ( (p = p.next) != null )
				if ( (Integer)p.data1 > (Integer)q.data1 ) 				
					swap(q, p);						
		} while ( (q = q.next) != null );
	}
	public void swap(node <T, Lt> q, node <T, Lt> p)
	{
		T tmp_d1_q = q.data1; 
		Lt tmp_d2_q = q.data2;
		
		q.data1 = p.data1; 
		q.data2 = p.data2;
		
		p.data1 = tmp_d1_q; 
		p.data2 = tmp_d2_q;
	}
	public void print()
	{
		node <T, Lt> q = head;
		do
		{
			System.out.println(q.data1);
			q = q.next;
		} while ( q != null );
	}
	
}
